So, we're going to use, we're going to look at essentially two search strategies.

One is called greedy search and the other one is called a star search, which is provably

the best you can do.

So I told you we want to use information outside the problem statement if we have it available.

If you think about Lord of the Rings, Gandalf and his people were kind of lost somewhere

in Moria and they had I think three tunnels they could go down to and at some point Gandalf

says well this one smells the best.

That is information, the smell is information that is outside the problem space really.

And we're going to look for smells, things like smells and the question is what should

smells be like so that we can actually make progress with them.

So the idea is that we're going to use, a smell is difficult to capture so we give ourselves

something we call an evaluation function which is really, tells us per node how desirable

it is.

The smells you usually find undesirable.

Where it doesn't smell good you don't go typically for good reasons.

So that's an evaluation function.

Every node we attach a desirability value to.

And then our strategy will essentially be to sort the queue in the order of desirability

and take out the most desirable node first.

Okay, that's exactly what Gandalf did.

Smells better, we're going there.

And if you do that, if you smell at every intersection and always take the best node,

you could imagine you're getting something.

We'll look at that.

So this basically always trying to go the best route, the best smelling route is called

greedy search.

One thing to note here, and that's very important, is that we've looked at uniform cost search.

And we've always took the cheapest one.

And here we're doing something very similar, not the cheapest one, but the best smelling

one.

And as we'll see, those are completely different things and they have drastically different

consequences.

So what you want to realize is that path costs, cheapest one, is always looking backwards.

I'm optimizing the costs I've already incurred.

Whereas smelling is essentially you look for the most desirable daughter node, which is

something where you're looking forward.

You're estimating, because you don't know, how long it will take you to Bucharest.

And you're going to go to that city where you have the feeling, oh, that is much nearer.

That's the nearest to Bucharest.

So we have something completely different here.

The smell we're going to use for Romania is essentially straight line distance to Bucharest.

And if something is near, then you see that on the map.

You're not actually going to go further away from Bucharest.

So that is something that there's two things to note here.

The straight line distance to Bucharest is actually not something that's given with the

problem.

Remember, the problem was a four-tuple.

States, actions, initial state, and goal states.

No straight line distance in there.

So we're going to use straight line distance as the evaluation function.